package Medium;

import Utils.Utils;

public class LC0215 {
    /**
     * 基于堆排序的方法。始终维护容量为K的小根堆；从第K+1个元素开始，如果元素比堆顶更小，则将堆顶替换为当前元素并维护堆；最后返回堆顶元素即可。
     * 时间复杂度在N到NlogN之间，为e^u+uN-N，其中ue^u=N。
     */
    public static int findKthLargest(int[] nums, int k) {
        adjustToMinHeap(nums, k);
        for (int i = k; i < nums.length; i++) {
            if (nums[i] > nums[0]) {
                int tmp = nums[0];
                nums[0] = nums[i];
                nums[i] = tmp;
                percolateDown(nums, 0, k);
            }
        }
        return nums[0];
    }

    /**
     * 基于快速排序的算法，与官方题解思路相同，期望的时间复杂度为O(N)。
     * 实际上会比官方实现时间长。
     */
    public static int findKthLargestByQuickSelect(int[] nums, int k) {
        return Utils.quickSelect(nums, k);
    }

    /**
     * 将前k个元素调整为小根堆
     */
    public static void adjustToMinHeap(int[] nums, int k) {
        for (int idx = k / 2 - 1; idx >= 0; idx--) { // k/2自带floor效果
            percolateDown(nums, idx, k);
        }
    }


    /**
     * 执行堆排序算法中的下滤操作。注意：原地操作。
     *
     * @param range 树中元素的个数，默认树的范围是nums[0~range-1]
     */
    private static void percolateDown(int[] nums, int idx, int range) {
        int cur = idx;
        while (true) {
            int leftChild = 2 * cur + 1, rightChild = 2 * cur + 2;
            if (leftChild >= range) break;
            int childIdx = -1, childValue = -1;
            if (nums[leftChild] < nums[cur]) { // 存在左孩子，且左孩子小于当前结点
                childIdx = leftChild;
                childValue = nums[leftChild];
            }
            if (rightChild < range && nums[rightChild] < Math.min(nums[cur], nums[leftChild])) { // 存在右孩子，且右孩子更小
                childIdx = rightChild;
                childValue = nums[rightChild];
            }
            // 交换
            if (childIdx >= 0) {
                int tmp = nums[cur];
                nums[cur] = childValue;
                nums[childIdx] = tmp;
                cur = childIdx;
            }
            else break; // 无需交换，终止循环
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{-1, 2, 0};
        System.out.println(findKthLargestByQuickSelect(nums, 3));
    }
}
